package com.hspedu.newData.dmsxl.设计题;

import com.hspedu.dmsxl.栈与队列.前k个高频元素347;
import com.hspedu.newData.dmsxl.ds.ListNode;

import java.util.Random;

/**
 * @Author: yh
 * @description: 
 * @CreateTime: 2025-05-21 
 * @Version: 1.0
 */

public class LC382链表随机节点 {

    class Solution {

        private ListNode head;
        private int size;
        private Random random;
        public Solution(ListNode head) {
            this.head = head;
            this.size = getSize(head);
            random = new Random();
        }

        public int getRandom() {
            int i = random.nextInt(size);
            int j = 0;
            ListNode cur = head;
            while (j<i){
                j++;
                cur = cur.next;
            }

            return cur.val;

        }

        private int getSize(ListNode head){
            int size = 0;
            while (head!=null){
                size++;
                head = head.next;
            }
            return size;
        }
    }
}
